package com.leetcode.partition20;

import java.io.*;
import java.util.PriorityQueue;

/**
 * @author `RKC`
 * @date 2022/2/1 17:01
 */
public class LC1976到达目的地的方案数 {

    private static final int N = 210, M = N * N, mod = (int) (1e9 + 7);
    private static int[] h = new int[N], e = new int[M], ne = new int[M], w = new int[M];
    private static int[] cnt = new int[N];
    private static long[] dist = new long[N];
    private static boolean[] st = new boolean[N];

    private static int n = 0, m = 0, idx = 0;

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] ss = reader.readLine().split(" ");
        int n = Integer.parseInt(ss[0]), m = Integer.parseInt(ss[1]);
        int[][] edges = new int[m][3];
        for (int i = 0; i < m; i++) {
            ss = reader.readLine().split(" ");
            int a = Integer.parseInt(ss[0]), b = Integer.parseInt(ss[1]), c = Integer.parseInt(ss[2]);
            edges[i] = new int[]{a, b, c};
        }
        writer.write(countPaths(n, edges) + "\n");
        writer.flush();
    }

    public static int countPaths(int _n, int[][] roads) {
        n = _n;
        m = roads.length;
        for (int i = 0; i < m; i++) {
            int a = roads[i][0], b = roads[i][1], c = roads[i][2];
            add(a, b, c);
            add(b, a, c);
        }
        return dijkstra();
    }

    private static int dijkstra() {
        for (int i = 0; i < N; i++) dist[i] = (long) 1e18;
        dist[0] = 0;
        cnt[0] = 1;
        PriorityQueue<Node> heap = new PriorityQueue<>((o1, o2) -> Long.compare(o1.w, o2.w));
        heap.add(new Node(0, 0));
        while (!heap.isEmpty()) {
            Node cur = heap.poll();
            int u = cur.u;
            if (st[u]) continue;
            st[u] = true;
            for (int i = h[u]; i != 0; i = ne[i]) {
                int v = e[i];
                if (dist[v] > dist[u] + w[i]) {
                    dist[v] = dist[u] + w[i];
                    cnt[v] = cnt[u];
                    heap.add(new Node(v, dist[v]));
                } else if (dist[v] == dist[u] + w[i]) cnt[v] = (cnt[v] + cnt[u]) % mod;
            }
        }
        for (int i = 0; i < n; i++) System.out.print(dist[i] + " ");
        System.out.println();
        for (int i = 0; i < n; i++) System.out.print(cnt[i] + " ");
        System.out.println();
        return cnt[n - 1];
    }

    private static void add(int a, int b, int c) {
        e[++idx] = b;
        ne[idx] = h[a];
        h[a] = idx;
        w[idx] = c;
    }

    private static class Node {
        private int u;
        private long w;

        public Node(int u, long w) {
            this.u = u;
            this.w = w;
        }
    }
}
